#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int dp[100][100];
        int dy[3] = { -1, 0, 1 };
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (i == 0) dp[i][j] = matrix[i][j];
                else
                {
                    int a = 1e9;
                    for (int k = 0; k < 3; k++)
                    {
                        int y = j + dy[k];
                        if (y >= 0 && y < n) a = min(a, dp[i - 1][y]);
                    }
                    dp[i][j] = a + matrix[i][j];
                }
            }

        int mi = 1e9;
        for (int i = 0; i < n; i++) mi = min(mi, dp[n - 1][i]);
        return mi;
    }
};